package data_structure.linkedList;

/**
 * @ClassName : data_structure.linkedList.SingleLinkedList
 * @Description : 类描述
 * Created by cyd on 2021-01-23 20:38:30
 */
public class SingleLinkedList {
    // 头节点
    private HeroNode head = new HeroNode(0, "头节点", "头节点");

    // 添加节点的方法，仅用于添加元首节点
    private void add(HeroNode node) {
        // 1.找到当前链表的最后一个节点
        // 2.将最后一个节点的next（数据域）指向新的节点
        HeroNode temp = head;
        while (temp.getNext() != null) {
            // 如果找到了最后一个节点，就终止循环，此时temp是最后一个节点
            // 每找到一个节点，就将temp后移一位
            temp = temp.getNext();
        }
        temp.setNext(node);
    }

    // 判断链表为空的方法
    public boolean isEmpty() {
        if (head.getNext() == null) {
            return true;
        }
        return false;
    }

    // 展示链表
    public void show() {
        if (this.isEmpty()) return;

        HeroNode temp = head;
        System.out.println(temp);
        while (temp.getNext() != null) {
            System.out.println(temp.getNext());
            temp = temp.getNext();
        }
    }

    // 按顺序插入
    public void addByOrder(HeroNode newNode) {
        if (this.isEmpty()) {
            this.add(newNode);
            return;
        }

        // 判断当前节点是否存在
        try {
            HeroNode thisNode = this.selectNodeByNo(newNode.getNo());
            if (thisNode == null) return;
        } catch (RuntimeException e) {
            System.out.println("可以按序插入此节点:" + newNode.toString());
        }
        // 没有异常，就找到此节点前一个节点
        HeroNode preNode = this.selectPreNodeByNo(newNode.getNo());
        newNode.setNext(preNode.getNext());
        preNode.setNext(newNode);
    }

    // 根据编号查找节点
    public HeroNode selectNodeByNo(Integer no) {
        if (this.isEmpty()) return null;

        HeroNode temp = head;
        while (temp.getNext() != null) {
            temp = temp.getNext();
            if (temp.getNo().equals(no)) return temp;
        }
        throw new RuntimeException("查找此节点时发现，没有这个索引");
    }

    // 查找当前节点的前一位
    private HeroNode selectPreNodeByNo(Integer no) {
        if (this.isEmpty()) return null;

        int i = no - 1;
        while (i < no) {
            HeroNode temp = head;
            while (temp.getNext() != null) {
                temp = temp.getNext();
                if (temp.getNo().equals(i)) {
                    return temp;
                }
            }
            i--;
            // 小于0，是为了保证no=1时的运行
            if (i <= 0) break;
        }

        return head;
    }

    // 修改节点
    public void update(HeroNode newNode) {
        if (this.isEmpty()) return;
        // 1.先判断有没有当前节点
        HeroNode currentNode = this.selectNodeByNo(newNode.getNo());
        if (currentNode != null) {
            // 2.找到当前节点的前一位
            HeroNode preNode = this.selectPreNodeByNo(newNode.getNo());
            // 3.修改
            newNode.setNext(currentNode.getNext());
            preNode.setNext(newNode);
        }
    }

    // 删除节点
    public void deleteNodeByIndex(Integer index) {
        if (this.isEmpty()) return;
        // 得到当前节点的前一个节点
        HeroNode preNodeByNo = this.selectPreNodeByNo(index);
        // 得到当前节点的后一个节点
        HeroNode nextNode = preNodeByNo.getNext().getNext();
        // 删除动作
        preNodeByNo.setNext(nextNode);
    }

    // 链表的长度
    public Integer size() {
        Integer length = 0;
        HeroNode temp = this.head;
        while (temp.getNext() != null) {
            temp = temp.getNext();
            length++;
        }
        return length;
    }

    // 查找链表中倒数第k个节点
    public HeroNode findK(Integer k) {
        if (k <= 0) throw new RuntimeException("不要乱来，k不可能为0和负数");
        Integer size = this.size();
        // 转化成求正数的节点
        Integer order = size - k + 1;
        if (order <= 0) throw new RuntimeException("链表长度为" + size + "请重新输入");
        HeroNode temp = head;
        while (order > 0) {
            temp = temp.getNext();
            order--;
        }
        return temp;
    }

    // 单链表的反转
    public SingleLinkedList revese() {
        Integer newIndex = this.size();
        SingleLinkedList revesedLinkedList = new SingleLinkedList();

        HeroNode temp = head;
        while (temp.getNext() != null) {
            temp = temp.getNext();
        }

        HeroNode endNode = temp;
        for (int i = 0; i < newIndex; i++) {
            this.deleteNodeByIndex(endNode.getNo());
            revesedLinkedList.add(endNode);
            endNode = this.selectPreNodeByNo(endNode.getNo());
        }

        return revesedLinkedList;
    }

    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addByOrder(new HeroNode(1, "songjiang", "jishiyu"));
        singleLinkedList.addByOrder(new HeroNode(2, "likui", "heixuanfeng"));
        singleLinkedList.addByOrder(new HeroNode(5, "lichong", "baozitou"));
        singleLinkedList.addByOrder(new HeroNode(3, "吴用", "智多星"));
        singleLinkedList.show();

//        System.out.println(singleLinkedList.size());
//        System.out.println("------------修改---------------");
//        singleLinkedList.update(new HeroNode(1, "松江", "及时雨"));
//        singleLinkedList.update(new HeroNode(5, "林冲", "豹子头"));
//        //singleLinkedList.update(new HeroNode(4, "林冲", "豹子头"));
//        singleLinkedList.show();
//        System.out.println(singleLinkedList.size());
//        System.out.println("-------------删除1和5--------------");
//        singleLinkedList.deleteNodeByIndex(5);
//        singleLinkedList.deleteNodeByIndex(1);
//        singleLinkedList.show();
//        System.out.println(singleLinkedList.size());
//        System.out.println("-------------查找倒数第k个节点--------------");
//        System.out.println(singleLinkedList.findK(5));
        System.out.println("-------------单链表的反转--------------");
        SingleLinkedList revesed = singleLinkedList.revese();
        revesed.show();

    }
}
